import java.util.Arrays;

/**
 * Description:
 * ��������?people?��people[i]��ʾ�� i?���˵�����?�������������ޣ�ÿ�Ҵ����Գ��ص��������Ϊ?limit��
 * <p>
 * ÿ�Ҵ�����ͬʱ�����ˣ�����������Щ�˵�����֮�����Ϊ?limit��
 * <p>
 * ���� �����������������С����?��
 * <p>
 * ?
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺people = [1,2], limit = 3
 * �����1
 * ���ͣ�1 �Ҵ��� (1, 2)
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/boats-to-save-people
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/4/2 16:04
 */
public class Solution_881 {

    public static void main(String[] args) {
        int[] arr = {0, 0, 0, 1, 5, 5, 5, 6, 7, 8, 9, 9, 9, 10};
        int limit = 10;
        arr = new int[]{2, 2, 2, 3, 3};
        limit = 6;
        System.out.println(numRescueBoats(arr, limit));
    }

    /**
     * ˼·��
     * 1����С��������
     * 2���ҵ���ʹpeopeo[i] * 2<limit�����ұߵ�lLessLimit
     * 3.1�����ⳡ�������ⳡ����peopeo���е�ֵ��2����С��limit
     * ��{2, 2, 2, 3, 3}��limit=6��
     * 3.2 ��L=lLessLimit,R=L+1��ʼ���������sum
     * ���1��sum<=limit,����һ���ϴ���lRAdd++��L--,R++
     * ���2��sum>limit,L--,ladd++
     * 4���𰸣�lRAdd+ladd/2����ȡ��+(N-R)
     *
     * @param people
     * @param limit
     * @return
     */
    public static int numRescueBoats(int[] people, int limit) {
        if (people == null || people.length == 0) {
            return 0;
        }
        Arrays.sort(people);
        int N = people.length;
        /**
         * ��֤���е�������0...limit����
         */
        if (people[N - 1] > limit || people[0] > limit) {
            return Integer.MAX_VALUE;
        }
        // С��limit/2�����Ҳ�λ�ã��Ѿ���С����������ˣ�
        int lLessLimit = N - 1;
        for (int i = 0; i < N; i++) {
            if (people[i] > limit / 2) {
                lLessLimit = i - 1;
                break;
            }
        }
        int lRAdd = 0;
        int ladd = 0;
        // ���м�������չ��
        int L = lLessLimit;
        int R = lLessLimit + 1;
        /**
         * ���ⳡ����peopeo���е�ֵ��2����С��limit
         */
        if (L == N - 1) {
            lRAdd = (int) (Math.ceil((double) N / 2));
        }
        while (L >= 0 && R < N) {
            int sum = people[L] + people[R];
            if (sum <= limit) {
                lRAdd++;
                L--;
                R++;
            } else {
                ladd++;
                L--;
            }

        }
        int ans = lRAdd + (int) Math.ceil((double) ladd / 2) + (N - R);
        return ans;
    }

}
